package code1_100.code81_90;

/**
 * 存在一个按升序排列的链表，给你这个链表的头节点 head ，请你删除链表中所有存在数字重复情况的节点，只保留原始链表中 没有重复出现 的数字。
 *
 * 返回同样按升序排列的结果链表。
 *
 * 输入：head = [1,2,3,3,4,4,5]
 * 输出：[1,2,5]
 *
 * 输入：head = [1,1,1,2,3]
 * 输出：[2,3]
 */
public class _82deleteDuplicates {

    /**
     * 1：遍历链表，使用头插法直接生成
     * 2：遍历链表，直接删除
     *
     * 忠告 ：
     * 1. 舍得用变量，千万别想着节省变量，否则容易被逻辑绕晕
     * 2. head 有可能需要改动时，先增加一个 假head，返回的时候直接取 假head.next，这样就不需要为修改 head 增加一大堆逻辑了。
     *
     * @param head
     * @return
     */
    public ListNode deleteDuplicates(ListNode head) {
        if(head==null||head.next==null)return head;
        ListNode dummy = new ListNode(0,head);
        int preVal = head.val;
        while (head.next!=null){
            if(preVal == head.next.val){
                // 如果有一个相等，直接便利到下一个不相等节点
                while (head!=null&&head.val==preVal){
                    head = head.next;
                }
            }
            preVal = head.val;
            head = head.next;
        }
        return dummy.next;
    }

    /**
     * 没写出来正确逻辑，题解方法.
     * 写一遍后的经验，上面自己写主要是头结点的选取，手足无措，看到这想到，应该善用dummy！上述问题迎刃而解！
     *
     * 执行用时：     * 0 ms     * , 在所有 Java 提交中击败了     * 100.00%     * 的用户
     * 内存消耗：     * 38.1 MB     * , 在所有 Java 提交中击败了     * 9.53%     * 的用户
     * @param head
     * @return
     */
    public ListNode deleteDuplicates1(ListNode head) {
        if(head == null||head.next==null)return head;
        ListNode dummy = new ListNode(0,head);
        ListNode cur = dummy;
        while (cur.next!=null&&cur.next.next!=null){
            if(cur.next.val == cur.next.next.val){
                int x = cur.next.val;
                while (cur.next!=null&&cur.next.val ==x){
                    cur.next = cur.next.next;
                }
            }else {
                cur = cur.next;
            }
        }
        return dummy.next;
    }

}
